package 题目集.扫描线;

import org.junit.Test;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * https://leetcode.cn/problems/minimum-interval-to-include-each-query/description/
 */
public class ch01_包含每个查询的最小区间 {
    /**
     * 朴素思路：
     *      对于每一个查询，都去遍历所有区间，取一个最小值
     *      时间复杂度n^2
     * 优化思路:离线+堆
     *      对区间按左端点排个序，查询也排个序。
     *      将所有左端点小于当前查询的区间放入小根堆，小根堆中存储区间的长度，和终点。
     *      对于当前查询，其查询结果为堆顶未过期元素。
     */
    PriorityQueue<int[]> queue;

    public int[] minInterval(int[][] intervals, int[] queries) {
        queue = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        int[][] issue = handle(intervals, queries);
        int cur = 0;
        for (int[] ask : issue) {
            for (; cur < intervals.length && intervals[cur][0] <= ask[0]; cur++) {
                int[] info = {intervals[cur][1] - intervals[cur][0] + 1, intervals[cur][1]};
                queue.add(info);
            }
            queries[ask[1]] = fun(ask[0]);
        }
        return queries; //把问题数组用来存放结果
    }

    /**
     * 查询v在堆中对应的最小长度
     * @param v
     * @return
     */
    public int fun(int v) {
        //将右端点比自己小的区间弹出
        while (!queue.isEmpty() && queue.peek()[1] < v) {
            queue.poll();
        }
        return queue.isEmpty() ? -1 : queue.peek()[0];
    }

    /**
     * 对区间排序，并返回一个排好序的询问数组。其中询问数组0位置是值，1位置是原下标
     */
    public static int[][] handle(int[][] intervals, int[] queries) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        int[][] ask = new int[queries.length][2];
        for (int i = 0; i < queries.length; i++) {
            ask[i][0] = queries[i];
            ask[i][1] = i;
        }
        Arrays.sort(ask, (a, b) -> a[0] - b[0]);
        return ask;
    }

    @Test
    public void test() {
        int[][] intervals = {{1, 4}, {2, 4}, {3, 6}, {4, 4}};
        int[] issue = {2, 3, 4, 5};
        int[] res = minInterval(intervals, issue);
        System.out.println(Arrays.toString(res));
    }
}
